import java.util.*;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/12/2 下午 03:32
 */
public class day1912 {

//    public static void main(String[] args) {
//        // TODO 输出最长对称字符串：goog
//        String input1 = "google";
//
//        // TODO 输出3个最长对称字符串：aba/aca/ada
//        String input2 = "abcda";
//
//        // TODO 输出2个最长对称字符串：pop/upu，不会输出特殊字符的对称字符串p-p
//        String input3 = "pop-upu";
//
//        System.out.println(Test1.findLCS(input1));
//        System.out.println(Test1.findLCS(input2));
//        System.out.println(Test1.findLCS(input3));
//
//    }

    static class Test1 {

        public static String[] stringFilter(String str) {
            String regEx = "[^a-zA-Z0-9]";
            Pattern p = Pattern.compile(regEx);
            return p.split(str);
        }

        private static void getAllLcs(String a, String b, int[][] mux, int i, int j, String path, Set<String> paths) {

            StringBuilder pathBuilder = new StringBuilder(path);
            while (i > 0 && j > 0) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    pathBuilder.append(a.charAt(i - 1));
                    --i;
                    --j;
                } else {
                    if (mux[i - 1][j] > mux[i][j - 1]) {
                        --i;
                    } else if (mux[i - 1][j] < mux[i][j - 1]) {
                        --j;
                    } else {
                        getAllLcs(a, b, mux, i - 1, j, pathBuilder.toString(), paths);
                        getAllLcs(a, b, mux, i, j - 1, pathBuilder.toString(), paths);
                        return;
                    }
                }
            }
            paths.add(pathBuilder.toString());
        }

        public static String findLCS(String input) {
            if (input == null || input.length() == 0) {
                return "";
            }

            // 要返回的结果
            StringBuilder result = new StringBuilder();

            // 将字符串反转
            String reverse = new StringBuilder(input).reverse().toString();

            // 字符串长度
            int len = input.length();

            // 矩阵 -> 二维数组
            int[][] tmp = new int[len + 1][len + 1];

            for (int i = 1; i < len + 1; i++) {
                for (int j = 1; j < len + 1; j++) {
                    if (input.charAt(i - 1) == reverse.charAt(j - 1)) {
                        tmp[i][j] = tmp[i - 1][j - 1] + 1;
                    } else {
                        tmp[i][j] = Math.max(tmp[i - 1][j], tmp[i][j - 1]);
                    }
                }
            }

            Set<String> paths = new HashSet<String>() {
            };
            Test1.getAllLcs(input, reverse, tmp, input.length(), reverse.length(), "", paths);

            return String.join("/", paths);
        }

        public static String maxs(String input) {
            String[] prepare = stringFilter(input);
            StringBuffer sb = new StringBuffer();
            for (String str : prepare) {
                String result = findLCS(str);
                sb.append(result);
                sb.append("/");
            }
            return sb.substring(0, sb.length() - 1);
        }
    }

    static class contest166 {
        public int subtractProductAndSum(int n) {
            int ret = 0, sum = 0, mul = 1;
            while (n > 0) {
                int temp = n % 10;
                sum += temp;
                mul *= temp;
                n /= 10;
            }
            ret = mul - sum;
            return ret;
        }

        public List<List<Integer>> groupThePeople(int[] groupSizes) {
            List<List<Integer>> ret = new ArrayList<>();
            HashMap<Integer, List<Integer>> hashMap = new HashMap<>();
            for (int i = 0; i < groupSizes.length; i++) {
                List<Integer> integerList = hashMap.getOrDefault(groupSizes[i], new ArrayList<>(groupSizes[i]));
                if (integerList.size() == groupSizes[i]) {
                    ret.add(integerList);
                    integerList = new ArrayList<>(groupSizes[i]);
                }
                integerList.add(i);
                hashMap.put(groupSizes[i], integerList);
            }
            ret.addAll(hashMap.values());
            return ret;
        }

        public int smallestDivisor(int[] nums, int threshold) {
            long left = 1;
            long right = 0;
            for (int num : nums) {
                right = Math.max(num, right);
            }
            while (left + 1 < right) {
                long mid = (left + right) >>> 1;
                if (calcSum(nums, mid) > threshold) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            if (calcSum(nums, 1) <= threshold) {
                return 1;
            }
            return (int) right;
        }

        private long calcSum(int[] nums, long mid) {
            long sum = 0;
            for (int num : nums) {
                sum += (num + mid - 1) / mid;
            }
            return sum;
        }

        public int minFlips(int[][] mat) {
            int row = mat.length, col = mat[0].length;
            Set<List<Integer>> initSet = new HashSet<>();
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (mat[i][j] == 1) {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        list.add(j);
                        initSet.add(list);
                    }
                }
            }
            if (initSet.size() == 0) {
                return 0;
            }

            Queue<Set<List<Integer>>> queue = new LinkedList<>();
            queue.add(initSet);
            Set<Set<List<Integer>>> visited = new HashSet<>();
            int step = 0;
            while (queue.size() > 0) {
                int qSize = queue.size();
                step++;
                for (int k = 0; k < qSize; k++) {
                    Set<List<Integer>> curSet = queue.poll();
                    for (int i = 0; i < row; i++) {
                        for (int j = 0; j < col; j++) {
                            Set<List<Integer>> newSet = new HashSet<>(curSet);
                            flip(newSet, i, j, row, col);
                            if (newSet.size() == 0) {
                                return step;
                            }
                            if (!visited.contains(newSet)) {
                                visited.add(newSet);
                                queue.add(newSet);
                            }
                        }
                    }
                }
            }
            return -1;
        }

        private void flip(Set<List<Integer>> curSet, int i, int j, int row, int col) {
            flipOne(curSet, i, j);
            int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (int[] dir : dirs) {
                int curI = i + dir[0], curJ = j + dir[1];
                if (curI < 0 || curI >= row || curJ < 0 || curJ >= col) {
                    continue;
                }
                flipOne(curSet, curI, curJ);
            }
        }

        private void flipOne(Set<List<Integer>> curSet, int i, int j) {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            list.add(j);
            if (curSet.contains(list)) {
                curSet.remove(list);
            } else {
                curSet.add(list);
            }
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static class contest167 {
        public int getDecimalValue(ListNode head) {
            StringBuilder builder = new StringBuilder("");
            builder.append(head.val);
            while (head.next != null) {
                ListNode next = head.next;
                builder.append(next.val);
                head = next;
            }
            return Integer.parseInt(builder.toString(), 2);
        }

        public List<Integer> sequentialDigits(int low, int high) {
            int[] two = {12, 23, 34, 45, 56, 67, 78, 89};
            int[] three = {123, 234, 345, 456, 567, 678, 789};
            int[] four = {1234, 2345, 3456, 4567, 5678, 6789};
            int[] five = {12345, 23456, 34567, 45678, 56789};
            int[] six = {123456, 234567, 345678, 456789};
            int[] seven = {1234567, 2345678, 3456789};
            int[] eight = {12345678, 23456789};
            int[] nine = {123456789};
            List<Integer> ret = new ArrayList<>();
            if (high >= two[two.length - 1]) {
                for (int i : two) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : two) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            if (high >= three[three.length - 1]) {
                for (int i : three) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : three) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            if (high >= four[four.length - 1]) {
                for (int i : four) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : four) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            if (high >= five[five.length - 1]) {
                for (int i : five) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : five) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            if (high >= six[six.length - 1]) {
                for (int i : six) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : six) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            if (high >= seven[seven.length - 1]) {
                for (int i : seven) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : seven) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            if (high >= eight[eight.length - 1]) {
                for (int i : eight) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : eight) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            if (high >= nine[nine.length - 1]) {
                for (int i : nine) {
                    if (i >= low) {
                        ret.add(i);
                    }
                }
            } else {
                for (int i : nine) {
                    if (high >= i && i >= low) {
                        ret.add(i);
                    }
                }
            }
            return ret;
        }

        private int[][] map;
        private int row, col;

        public int maxSideLength(int[][] mat, int threshold) {
            row = mat.length;
            col = mat[0].length;
            formatArr(mat);
            int low = 0, high = Math.max(row, col) + 1;
            while (low < high) {
                int mid = (low + high) >>> 1;
                boolean flag = false;
                for (int i = 0; i + mid - 1 < row; i++) {
                    for (int j = 0; j + mid - 1 < col; j++) {
                        int sum = sum(i, j, i + mid - 1, j + mid - 1);
                        if (sum <= threshold) {
                            flag = true;
                        }
                    }
                }
                if (flag) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low - 1;
        }

        private void formatArr(int[][] mat) {
            map = new int[row + 1][col + 1];
            for (int i = 1; i <= row; i++) {
                int cur = 0;
                for (int j = 1; j <= col; j++) {
                    cur += mat[i - 1][j - 1];
                    map[i][j] = map[i - 1][j] + cur;
                }
            }
        }

        private int sum(int row1, int col1, int row2, int col2) {
            return map[row2 + 1][col2 + 1] - map[row2 + 1][col1] - map[row1][col2 + 1] + map[row1][col1];
        }

        private int[][][] maps;

        public int shortestPath(int[][] grid, int k) {
            maps = new int[41][41][41 * 41];
            if (grid[0][0] == 1) {
                if (k == 0) {
                    return -1;
                }
                k--;
                grid[0][0] = 0;
            }
            for (int i = 0; i < maps.length; i++) {
                for (int j = 0; j < maps[i].length; j++) {
                    Arrays.fill(maps[i][j], -1);
                }
            }
            row = grid.length;
            col = grid[0].length;
            int ret = DFS(0, 0, grid, k);
            if (ret == Integer.MAX_VALUE / 4) {
                return -1;
            }
            return ret;
        }

        private int DFS(int i, int j, int[][] grid, int k) {
            if (i == row - 1 && j == col - 1) {
                return 0;
            }
            int ans = maps[j][j][k];
            if (ans != -1) {
                return ans;
            }
            int[] dr = {0, 1, 0, -1};
            int[] dc = {1, 0, -1, 0};
            ans = Integer.MAX_VALUE / 4;
            for (int l = 0; l < 4; l++) {
                int newI = i + dr[l], newJ = j + dc[l];
                if (0 <= newI && newI < row && 0 <= newJ && newJ < col) {
                    if (grid[newI][newJ] == 1 && k > 0) {
                        ans = Math.min(ans, DFS(newI, newJ, grid, k - 1) + 1);
                    } else if (grid[newI][newJ] == 0) {
                        ans = Math.min(ans, DFS(newI, newJ, grid, k) + 1);
                    }
                }
            }
            return ans;
        }

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class contest169 {
        public int[] sumZero(int n) {
            int[] ret = new int[n];
            int maxNum = n / 2;
            int index = 0;
            if (n % 2 == 0) {
                while (maxNum > 0) {
                    ret[index++] = maxNum;
                    ret[index++] = -maxNum;
                    maxNum--;
                }
            } else {
                ret[index++] = 0;
                while (maxNum > 0) {
                    ret[index++] = maxNum;
                    ret[index++] = -maxNum;
                    maxNum--;
                }
            }
            return ret;
        }

        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            List<Integer> ret = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            if (root1 != null) {
                queue.add(root1);
                while (!queue.isEmpty()) {
                    TreeNode node = queue.poll();
                    ret.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
            }
            if (root2 != null) {
                queue.add(root2);
                while (!queue.isEmpty()) {
                    TreeNode node = queue.poll();
                    ret.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
            }
            ret.sort(null);
            return ret;
        }

        public boolean canReach(int[] arr, int start) {
            return recursive(arr, start, new HashSet<>());
        }

        private boolean recursive(int[] arr, int start, Set<Integer> exist) {
            if (start < 0 || start >= arr.length) {
                return false;
            }
            if (exist.contains(start)) {
                return false;
            }
            if (arr[start] == 0) {
                return true;
            }
            exist.add(start);
            int val = arr[start];
            start += val;
            boolean right = recursive(arr, start, exist);
            start -= val * 2;
            boolean left = recursive(arr, start, exist);

            return left || right;
        }

        private String[] words;

        private String result;

        public boolean isSolvable(String[] words, String result) {
            this.words = words;
            this.result = result;
            int maxWordLength = Arrays.stream(words).mapToInt(String::length).max().orElse(0);
            if (result.length() < maxWordLength) {
                return false;
            }
            Mapper mapper = new Mapper();
            return solvable(mapper, 0, 0);
        }

        private boolean solvable(Mapper mapper, int place, int increase) {
            if (place >= result.length()) {
                return increase == 0;
            }

            List<Character> inputChars = new ArrayList<>();
            for (String word : words) {
                if (word.length() > place) {
                    inputChars.add(word.charAt(word.length() - 1 - place));
                }
            }
            return solvableNext(mapper, place, increase, inputChars, 0);
        }

        private boolean solvableNext(Mapper mapper, int place, int increase, List<Character> inputChars, int charI) {
            while (charI < inputChars.size()) {
                char c = inputChars.get(charI);
                if (!mapper.hasValue(c)) {
                    for (int digit = 0; digit < 10; digit++) {
                        if (!mapper.canSet(digit)) {
                            continue;
                        }
                        Mapper next = new Mapper(mapper);
                        next.set(c, digit);
                        if (solvableNext(next, place, increase, inputChars, charI + 1)) {
                            return true;
                        }
                    }
                    return false;
                }
                charI++;
            }

            int sum = inputChars.stream().mapToInt(mapper::get).sum() + increase;
            int resultValue = sum % 10;
            char resultChar = result.charAt(result.length() - 1 - place);
            if (mapper.hasValue(resultChar)) {
                if (mapper.get(resultChar) != resultValue) {
                    return false;
                }
            } else {
                if (!mapper.canSet(resultValue)) {
                    return false;
                }
                mapper.set(resultChar, resultValue);
            }
            return solvable(mapper, place + 1, sum / 10);
        }

        private static class Mapper {
            private int[] alphabet = new int[26];
            private Set<Integer> leftDigits = new HashSet<>();

            public Mapper() {
                Arrays.fill(alphabet, -1);
                leftDigits.addAll(IntStream.range(0, 10).boxed().collect(Collectors.toList()));
            }

            public Mapper(Mapper template) {
                System.arraycopy(template.alphabet, 0, alphabet, 0, 26);
                leftDigits.addAll(template.leftDigits);
            }

            public boolean hasValue(char c) {
                return alphabet[c - 'A'] >= 0;
            }

            public int get(char c) {
                return alphabet[c - 'A'];
            }

            public boolean canSet(int v) {
                return leftDigits.contains(v);
            }

            public void set(char c, int v) {
                leftDigits.remove(v);
                alphabet[c - 'A'] = v;
            }
        }

    }

    public static void main(String[] args) {
        contest167 contest167 = new contest167();
    }

}
